package algorithm;

import structure.ListNode;

/**
 * 142. 环形链表
 *      给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
 */
public class LeetCode_detectCycle_142 {
    public ListNode detectCycle(ListNode head) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode curr = dummy;
        ListNode lower = curr;
        ListNode fast = curr.next;

        // 下面的和部分判断会在没有环的情况下出现空指针异常
        // 具体的分析如下：
            //[1,2]不存在环
            // 一开始的结构 .——> 1 ——> 2，初始: lower = .，fast = 1。
            // ① while语句的判断是正常的，此时lower = 1，fast = null
            // ② while语句出现问题，fast 已经是 null，fast.next 出现异常
//        while (fast.next != null && lower != null) {
//            fast = fast.next.next;
//            lower = lower.next;

        while (fast != null) {
            lower = lower.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            // 说明有环
            if (fast == lower) {
                while(curr != lower.next) {
                    curr = curr.next;
                    lower = lower.next;
                    // 这部分的判断是没用的，能进来说明肯定是已经有环， 那肯定能出去并且出去的时候curr == lower.next
//                    if (curr == lower.next) {
//                        return curr;
//                    }
                }
                return curr;
            }

        }
        return null;
    }
}
